package tulingxueyuan117;

import java.util.HashSet;

/**
 * Author: Zhang Dongwei
 * Date: 2022/10/23 13:39
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class p15_相交链表_160_re {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
      }
  }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(8);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        ListNode listNode7 = new ListNode(1);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        listNode5.next = listNode6;
        listNode6.next = listNode7;
        listNode7.next = listNode2;

        ListNode res = getIntersectionNode(listNode, listNode5);
        System.out.println(res.val);
    }

//    自己写的hashset,可以通过，但是效果不好
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        HashSet<ListNode> map = new HashSet<>();
        while (headA!=null){
            map.add(headA);
            headA = headA.next;
        }
        while (headB!=null){
            if(map.contains(headB)){
                return headB;
            }else {
                headB = headB.next;
            }
        }
        return null;
    }

//    双指针
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB){
        if(headA==null) return null;
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1!=p2){
            if(p1==null){
                p1 = headB;
            }else{
                p1 = p1.next;
            }
            if(p2==null){
                p2 = headA;
            }else {
                p2 = p2.next;
            }
        }
        return p1;
    }
}
